package Datas_Structure.Tree;

import java.util.*;

/**
 * 赫夫曼编码
 * 以赫夫曼树进行排序，路径左0右1
 * 非定长编码：
 * 字符的编码都不能是其它字符编码的前缀，符合此要求的编码叫前缀编码。
 */
public class codingNode implements Comparable<codingNode> {
    //字符
    Byte data;
    //权值
    int value;

    @Override
    public String toString() {
        return "codingNode{" +
                "data=" + data +
                ", value=" + value +
                '}';
    }

    //左节点
    codingNode lNode;
    //右节点
    codingNode rNode;

    public codingNode(Byte data, int value) {
        this.data = data;
        this.value = value;
    }

    @Override
    public int compareTo(codingNode o) {
        return o.value-this.value;
    }
}

class codingNodeTest {
    public static void main(String[] args) {
        String str = "can you can a can as a can canner can a can.";
        //转换为bytes数组
        byte[] bytes = str.getBytes();
        //进行赫夫曼编码
        byte[] b = HuffmanZip(bytes);
    }

    /**
     * 进行赫夫曼编码压缩的方法
     */
    private static byte[] HuffmanZip(byte[] bytes) {
        //先统计每一个byte出现的次数
        List<codingNode> nodes = getNdoes(bytes);
        //创建一颗赫夫曼树
        codingNode tree = creatTree(nodes);
       /* System.out.println(tree);
        System.out.println(tree.lNode);
        System.out.println(tree.rNode);*/
        //创建一个赫夫曼编码表
        Map<Byte,String> map = getHufferCOdes(tree);
        System.out.println(map.entrySet());
        //编码
        return null;
    }

    /**
     * 编码表
     * @param tree
     * @return
     */
    //临时变量存储路径
    static StringBuilder sb = new StringBuilder();
    //存贮赫夫曼编码
    static Map<Byte,String> huffCodes = new HashMap<>();

    private static Map<Byte, String> getHufferCOdes(codingNode tree) {
        if (tree == null){
            return null;
        }
        getHufferCOdes(tree.lNode,"0",sb);
        getHufferCOdes(tree.rNode,"1",sb);
        return huffCodes;
    }
    private static void getHufferCOdes(codingNode node, String code, StringBuilder sb) {
        StringBuilder sb2 = new StringBuilder(sb);
        sb2.append(code);
        if (node.data==null){
            getHufferCOdes(node.lNode,"0",sb2);
            getHufferCOdes(node.rNode,"1",sb2);
        }else {
            huffCodes.put(node.data,sb2.toString());
        }
    }

    /**
     * 创建一个树的方法
     * @param nodes
     * @return
     */
    private static codingNode creatTree(List<codingNode> nodes) {
        while (nodes.size() > 1){
            //排序
            Collections.sort(nodes);
            //取出两个权值最低的二叉树
            codingNode l = nodes.get(nodes.size()-1);
            codingNode r = nodes.get(nodes.size()-2);
            //创建一颗新树
            codingNode codingNode = new codingNode(null, l.value + r.value);
            ////把前边的两个赋给新创建的树
            codingNode.lNode=l;
            codingNode.rNode=r;
            //把前边的两个删除
            nodes.remove(r);
            nodes.remove(l);
            //把新创建的二叉树放入集合中
            nodes.add(codingNode);
        }
        return nodes.get(0);
    }

    /**
     * 统计出现的次数的方法
     * @param bytes
     * @return
     */
    private static List<codingNode> getNdoes(byte[] bytes) {
        ArrayList<codingNode> list = new ArrayList<>();
        //创建一map集合
        HashMap<Byte,Integer> map = new HashMap<>();
        //统计每一个byte出现的次数
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);
            if (count == null){
                map.put(aByte,1);
            }else {
                map.put(aByte,count+1);
            }
        }
        //把每一个键值对转换为一个node对象
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            list.add(new codingNode(entry.getKey(), entry.getValue()));
        }
        return list;
    }
}